1. Field of the Invention
The present invention relates to a divider, and particularly to the configuration of a divider in which the divisor is a fixed constant.
2. Description of the Related Art
The circuit configuration of dividers known in the prior art that are constructed from, for example, integrated circuits take as a basis a subtraction process in which the quotient is the number of times the divisor can be subtracted from the dividend and the balance is the remainder. Devices taking the subtraction process as a basis adopt a variety of methods of accelerating the processing speed. The number of subtractions is reduced by repeatedly obtaining the remainder (partial remainder) and the quotient (partial quotient) by subtracting the divisor from the higher-order digit of the dividend and then obtaining the quotient and remainder of the next column by again subtracting the divisor from the sum of this remainder and the succeeding digit.
The number of processes can be further reduced in cases in which the divisor is a pre-determined constant. For example, Japanese Patent Laid-open No. 88334/86 describes a case in which the quotient and remainder are stored in a memory for a figures assumed in advance to be dividends, following which the memory is addressed by the dividend to extract the quotient and remainder. However, a massive amount of memory is required if the figures presupposed as the dividend are set to infinity, and consequently, the quotient and remainder for all numbers of a set digit number are set in memory, the memory is addressed from the higher-order digits of the dividend and partial quotients and partial remainders obtained, and the same processes repeated for numbers resulting from addition of these partial remainders to obtain the final quotient and remainder.
A large number of division processes are thus required if a division process is repeated. For example, a processing time of at least one control clock is required for each division process, and the processing time increases in accordance with the number of digits or the number of bits of the dividend. This problem will be further explained with reference to the accompanying figures.
FIG. 1 is a block diagram showing the divider described in Japanese Patent Laid-open No. 88334/86, FIG. 2A is a flowchart of the processes of this divider, and FIGS. 2B and 2C are flowcharts showing the state of the operation register. As shown in FIG. 1, the dividend is sent by way of line 500 and is then set to operation register 504 under the control of selector 506. The higher-order bit information of the dividend stored in operation register 504 passes by way of line 503 and is applied to division memory 505 as an address, and a partial remainder and partial quotient are each outputted to line 501 and line 502, respectively. The partial remainder of line 501, together with the lower-order bit information of the dividend that has not undergone the operation process that is supplied from line 507, are again set to operation register 504 by way of selector 506. The higher-order bit information that is thus set again to operation register 504 is subjected to the division process using division memory 505, and a similar division process is repeated until the value within operation register 504 is less than the divisor.
An explanation will next be presented using FIG. 1 and FIGS. 2A-2C which illustrate a concrete operation in which the 3 higher-order bits from operation register 504 are taken as the object of the division process, the binary number value of dividend being "1111b" and the binary number value of the divisor being "10b" (b indicating that these are binary numbers). In the first subtraction process loop, the 3 higher-order bits of dividend "1111b" set to operation register 504 (i.e., "111b") are applied to division memory 505 as an address by way of line 503. The values for the partial quotient "11b" and partial remainder "1b" are set in advance at address "111b" and are outputted from lines 501 and 502. Partial quotient, partial remainder, and the remaining bits of dividend are reset to operation register 504 by means of selector 506 and value obtained. The partial quotient "11b" outputted by way of line 502 is set to the lower-order bit 601 of operation register 504. The partial remainder "1b" outputted by way of line 501 is set to the higher-order bit 602 of operation register 504. The remaining bits of the dividend are set between the partial quotient and partial remainder following the partial quotient. The value of operation register 504 is thus "1111b" as a result of the first division process loop. Next, the higher-order bit "11b" made up by the partial remainder "1b" and the remaining bit "1b" of the dividend is still greater than the divisor "10b", and this value is therefore added to division memory 505 as an address by way of line 503, and the second division process loop is carried out. The partial quotient "1b" and partial remainder "1b" are set at address "11b" of division memory 505. The partial quotient "1b" is set to the lower-order bit 603 of operation register 504, the partial remainder "1b" is set to the higher-order bit 604, and the first partial quotient "11b" is shifted to the higher order of lower-order bit 603. As a result, the higher-order bit "1b" apart from partial quotients 605 and 603 becomes smaller than the divisor "10b", thereby completing the division process, and the value "111b", which is the combination of partial quotients 605 and 603, is taken as the final quotient, and the last remainder "1b" is taken as the final remainder.
The division process is thus repeated a plurality of times despite the use of memory and division cannot be realized in a single process, which is the minimum number of processes, and the processing time is protracted. Reducing the number of bits taken from operation register 504 and used to address the division memory decreases the amount of memory required, but also increases the number of loops of division processing and lengthens the processing time. On the other hand, increasing the number of bits used to address the division memory shortens the processing time but increases the amount of memory required by an exponent of the number of bits.
Japanese Patent Laid-open No. 190928/90 discloses an example in which a comparator circuit and a decoder are used in place of the memory that is used in the above-described example of the prior art. This device replaces division memory 505 of FIG. 1 with a divider that employs a comparator circuit and decoder, provides a plurality of comparator circuits that compare an integer power of the divisor with the bits to be divided of the dividend, calculates partial quotients and partial remainders by decoding the output of this plurality of comparator circuits at the decoder, and in the same way as the prior-art example of FIG. 1, takes the combination of partial quotients as the final quotient and the last remainder as the final remainder.
As with the prior-art example employing a memory (Japanese Patent Laid-open No. 88334/86), this example of the prior art entails a plurality of division processes and a protracted processing time. Moreover, as in the other prior-art example that uses a memory, the number of comparator circuits in this example increases with the number of bits of the object division for which partial quotients are produced, but this example raises an additional problem in that comparator circuits require far more space than a case using memory.